package org.Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class E03Leetcode49 {

    /*
        方法一：
        将排序后的字符串作为key
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> groups = new HashMap<>();

        for (String str : strs) {
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String new_str = new String(ch);
            List<String> list = groups.get(new_str);
            if (list == null) {
                list = new ArrayList<>();
                groups.put(new_str, list);
            }
            list.add(str);
        }

        return new ArrayList<>(groups.values());
    }

    /*
        方法二：
            将26个字母出现的次数作为key
     */
    static class ArrayKey{
        int[] key = new int[26];

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ArrayKey arrayKey = (ArrayKey) o;
            return Arrays.equals(key, arrayKey.key);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(key);
        }

        public ArrayKey(String str) {
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                int index = c - 'a';
                key[index] ++;
            }
        }
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<ArrayKey,List<String>> result = new HashMap<>();
        for (String str : strs){
            ArrayKey key = new ArrayKey(str);
            if(result.containsKey(key)){
                result.get(key).add(str);
            }else{
                List<String> list = new ArrayList<>();
                list.add(str);
                result.put(key,list);
            }
        }

        return new ArrayList<>(result.values());
    }

    public static void main(String[] args) {
        String[] strs = { "eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(new E03Leetcode49().groupAnagrams(strs));
    }

}
